package com.zjsru.plan2024.normal;

/**
 * 2924. 找到冠军 II
 * @Author: cookLee
 * @Date: 2024-04-14
 */
public class FindChampion2 {

    /**
     * 主
     * \
     * 给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [ui, vi] 表示图中存在一条从 ui 队到 vi 队的有向边。
     * 从 a 队到 b 队的有向边意味着 a 队比 b 队 强 ，也就是 b 队比 a 队 弱 。
     * \
     * 输入：n = 3, edges = [[0,1],[1,2]]
     * 输出：0
     * 解释：1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。
     * \
     * 输入：n = 4, edges = [[0,2],[1,3],[1,2]]
     * 输出：-1
     * 解释：2 队比 0 队和 1 队弱。3 队比 1 队弱。但是 1 队和 0 队之间不存在强弱对比。所以答案是 -1 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindChampion2 findChampion2 = new FindChampion2();
        int n = 3;
        int[][] edges = new int[][]{{0,2},{1,3},{1,2}};
        System.out.println(findChampion2.findChampion(n, edges));
    }

    /**
     * 寻找冠军：遍历
     *
     * @param n     n
     * @param edges 边缘
     * @return int
     */
    public int findChampion(int n, int[][] edges) {
        //定义一个数组记录输家
        boolean[] isLoser = new boolean[n + 1];
        for (int[] edge : edges) {
            //右边的总是输家
            isLoser[edge[1]] = true;
        }
        //按照球队依次寻找赢家
        int winner = -1;
        for (int i = 0; i < n; i++) {
            //此时球队已经输了,不需要在找胜者了
            if (isLoser[i]) {
                continue;
            }
            //只能存在一个冠军，满足此条件说明有向图可能没有互相比较
            if (winner != -1) {
                return -1;
            }
            winner = i;
        }
        return winner;
    }

}
